package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandTest {
	public static void main(String[] args) {
		String expression = "4.1+((3-1)/2)+5";

		PolandTest polandTest = new PolandTest();
		List<String> expressionList = polandTest.toList(expression);
		System.out.println("中序表达式对应列表:" + expression);

		List<String> SuffixExpressionList = polandTest.parseSuffixExpressionList(expressionList);
		System.out.println("后序表达式对应列表:" + SuffixExpressionList);

		float result = polandTest.culSuffixExpression(SuffixExpressionList);
		System.out.println("结果为：" + result);

	}

	public boolean isOper(String ch) {
		return ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/");
	}

	public int pripority(String ch) {
		if (ch.equals("+") || ch.equals("-")) {
			return 0;
		} else if (ch.equals("*") || ch.equals("/")) {
			return 1;
		} else {
			return -1;
		}
	}

	public float calculate(float num1, float num2, String oper) {
		if (oper.equals("+")) {
			return num2 + num1;
		} else if (oper.equals("-")) {
			return num2 - num1;
		} else if (oper.equals("*")) {
			return num2 * num1;
		} else if (oper.equals("/")) {
			return num2 / num1;
		} else {
			throw new RuntimeException("计算出错");
		}
	}

	public List<String> toList(String s) {
		List<String> expressionList = new ArrayList<>();
		PolandTest polandTest = new PolandTest();
		String item = "";
		for (int i = 0; i < s.length(); i++) {
			item += s.charAt(i);
			if (i == s.length() - 1 || polandTest.isOper(s.charAt(i) + "")
					|| s.charAt(i) == '(' || s.charAt(i) == ')' || polandTest.isOper(s.charAt(i + 1) + "")
					|| s.charAt(i + 1) == '(' || s.charAt(i + 1) == ')') {
				expressionList.add(item);
				item = "";
			}
		}
		return expressionList;
	}

	public List<String> parseSuffixExpressionList(List<String> list) {

		PolandTest polandTest = new PolandTest();
		//定义一个符号栈，和一个中间结果队列
		Stack<String> operStack = new Stack<>();
		List<String> midList = new ArrayList<>();

		int index = 0;
		while (index < list.size()) {
			if (polandTest.isOper(list.get(index))) {
				if (operStack.empty()) {
					operStack.push(list.get(index));
				} else {
					if (polandTest.pripority(list.get(index)) <= polandTest.pripority(operStack.peek())) {
						midList.add(operStack.pop());
					}
					operStack.push(list.get(index));
				}
			} else {
				if (list.get(index).equals("(")) {
					operStack.push(list.get(index));
				} else if (list.get(index).equals(")")) {
					if (!list.get(index + 1).equals("(")) {
						midList.add(operStack.pop());
					}
					operStack.pop();
				} else {
					midList.add(list.get(index));
				}
			}
			index++;
		}
		while (!operStack.empty()) {
			midList.add(operStack.pop());
		}
		return midList;
	}

	public float culSuffixExpression(List<String> suffixExpression) {
		float num1 = 0;
		float num2 = 0;
		String oper = "";
		float result = 0;
		PolandTest polandTest = new PolandTest();

		Stack<String> stack = new Stack<>();

		for (int i = 0; i < suffixExpression.size(); i++) {
			if (polandTest.isOper(suffixExpression.get(i))) {
				num1 = Float.parseFloat(stack.pop());
				num2 = Float.parseFloat(stack.pop());
				oper = suffixExpression.get(i);
				result = polandTest.calculate(num1, num2, oper);
				stack.push("" + result);
			} else {
				stack.push(suffixExpression.get(i));
			}
		}
		result = Float.parseFloat(stack.pop());
		return result;
	}
}
